package sort.quick;

public class findKth1 {
    public int findKth (int[] a, int n, int K) {
        // 快排
        quck_sort(a,0,a.length-1);
        //返回 len - k 的值
        return a[a.length-K];
    }
    void quck_sort(int[] a,int start,int end) {
        if(start < end){//判断条件
            int base = a[start];
            int left = start;
            int right = end;
            while(left < right) {
                while(left < right && a[right] >= base) {
                    right--;
                }
                //a[right] 比 base 小，替换a[left]
                a[left] = a[right];

                while(left < right && a[left] <= base) {
                    left++;
                }
                //a[left] 比 base 大，替换a[right]
                a[right] = a[left];
            }
            //left == right,a[left]左边比base小，右边比base大
            a[left] = base;
            quck_sort(a,start,left-1);//快排左子数组
            quck_sort(a,left+1,end);//快排右子数组

        }


    }
}
